1. Field of The Invention
The invention relates to methods and devices for sub-pixel accurate motion vector estimation and motion-compensated interpolation or prediction, as well as to a television apparatus comprising such a sub-pixel accurate motion-compensated interpolation device.
2. Description of the Related Art
Motion vectors are used in a range of image processing applications, such as coding, noise reduction, and scan rate conversion. Some of these applications, particularly the scan rate conversion applications, require the true motion of objects to be estimated (see Refs. [1], [2]). Other applications, e.g., coding and interlaced to sequential scan conversion, demand a high accuracy of the motion vectors to realize a low amplitude of remaining coding error, or alias, respectively (see Refs. [3], [4]). Finally there is a category of applications, e.g., consumer applications of motion estimation, where the cost of the motion estimator is of crucial importance (see Ref. [5]).
Several algorithms have been proposed to realize true motion estimation (Refs. [1], [2], [5], [6], [7], and [8]). Also algorithms have been proposed to realize motion estimation at a low complexity level, e.g., Refs. [5], [8], [9], [10] and [11], and apart from the pel-recursive algorithms that usually allow sub-pixel accuracy, see, e.g., Refs. [12], or [13], also a number of block-matching algorithms have been reported that allow the estimation of highly accurate motion vectors (see Refs. [1], [14], and [15]).
In a non-symmetrical motion estimator, it is tried to match a shifted portion of a previous (or next) image to a fixed portion of the present image. If the estimator is a block matcher, its error measure, using the Summed Absolute Difference (SAD) criterion, is:                               SAD          ⁡                      (                                          C                _                            ,                              X                _                            ,              n                        )                          =                              ∑                                          x                _                            ∈                              B                ⁡                                  (                                      x                    _                                    )                                                              ⁢                      xe2x80x83                    ⁢                      "LeftBracketingBar"                                          F                ⁡                                  (                                                                                    x                        _                                            -                                                                        C                          _                                                ⁡                                                  (                                                                                    X                              _                                                        ,                            n                                                    )                                                                                      ,                                          n                      -                      1                                                        )                                            -                              F                ⁡                                  (                                                            x                      _                                        ,                    n                                    )                                                      "RightBracketingBar"                                              (        1        )            
where C is the candidate vector under test, X indicates the position of the block B(X), F(x, n) is the luminance signal, and n the picture or image number. The resulting motion vectors describe the velocity of the block in the current image.
In a symmetrical motion estimator, two portions from two (usually successive) images are shifted in opposite direction, again, such that the optimal match results. The match error results as:                               SAD          ⁡                      (                                          C                _                            ,                              X                _                            ,              n                        )                          =                              ∑                                          x                _                            ∈                              B                ⁡                                  (                                      x                    _                                    )                                                              ⁢                      xe2x80x83                    ⁢                      "LeftBracketingBar"                                          F                ⁡                                  (                                                                                    x                        _                                            -                                              α                        ⁢                                                                              C                            _                                                    ⁡                                                      (                                                                                          X                                _                                                            ,                              n                                                        )                                                                                                                ,                                          n                      -                      1                                                        )                                            -                              F                ⁡                                  (                                                            x                      _                                        ,                                                                  +                                                  (                                                      1                            -                            α                                                    )                                                                    ⁢                                                                        C                          _                                                ⁡                                                  (                                                                                    X                              _                                                        ,                            n                                                    )                                                                                      ,                    n                                    )                                                      "RightBracketingBar"                                              (        2        )            
The resulting motion vectors (sum of the two shifts, after inverting one of them) describe the velocity of the block in an (not available) image positioned in between the two shifted images. The parameter xcex1, which lies between 0 and 1, determines the temporal position. This type of motion estimator is particularly relevant for frame rate conversion applications.
This disclosure addresses the problem of true-motion estimation with sub-pixel accuracy, where the vectors need to be valid at a point in time that lies between two input pictures (or images). This is particularly relevant for estimators applied in scan rate converters. Sub-pixel accuracy requires the interpolation of pixels at positions between given pixel values. The commonly used method is the so-called bi-linear interpolation, which is attractive for implementation because of its low complexity.
It is, inter alia, an object of the invention to provide an improved motion vector estimation and motion-compensated interpolation. To this end, the invention provides methods and devices for motion vector estimation and motion-compensated interpolation or prediction.
It is to be noted that in G. de Haan""s dissertation xe2x80x9cMotion estimation and compensation; An integrated approach to consumer display field rate conversionxe2x80x9d, Eindhoven 1992, section 8.1.1, a method is described to obtain first and second integer vectors (i.e., having only integer vector components) from an integer candidate vector (i.e., also having only integer vector components), to prevent sub-pixel interpolation for odd candidate vectors. For odd candidate vectors, i.e., a vector having an odd vertical component, a multiplication by a fraction of 0.5 results in a non-integer vector component. For candidate vectors having an even vertical component, there is no problem, as no non-integer value results from multiplying that even vertical component by a fraction of 0.5. This known method includes the steps of multiplying the vector components of the integer candidate vector by a fraction to obtain fractional vector components, rounding the fractional vector components to obtain integer vector components of the first vector, and subtracting the integer first vector from the integer candidate vector to obtain the integer second vector, so that the second vector also has only integer vector components.
In the description and claims, the term xe2x80x9croundingxe2x80x9d encompasses both a rounding down (or up) towards the largest smaller (or smallest larger) integer value (i.e., a truncation), and a rounding towards the nearest integer value. The expression xe2x80x9cimagexe2x80x9d encompasses both a field and a frame.
These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.